package seqlist.LeetCode;
//92. 反转链表 II
//给你单链表的头指针 head 和两个整数left 和 right ，其中left <= right 。
// 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

/**
 *思路一：迭代法。找到left节点的前驱，所以需要一个虚拟头节点，循环left - 1次就可以找到
 * 第一个翻转节点到最后肯定是在末尾的，所以用指针node执行它并保持不动，每次更新它执行的地址，
 * node后面的节点都需要进行头插，用cur执行。prve就是前驱的地址。每次都要更新prve.next
 * 和 node.next的地址
 */

/*

public class Num_92_reverseBetween {

    public ListNode reverseBetween(ListNode head, int left, int right) {

        //当链表为空或者 只有一个是时候，就不需要翻转链表了
        if(head == null || head.next == null){
            return head;
        }

        ListNode dummyHead = new ListNode();
        ListNode prve = dummyHead;
        dummyHead.next = head;

        //寻找left - 1次找到前驱位置
        for (int i = 0; i < left - 1; i++) {
            prve = prve.next;
        }//出来后此时的prve就是待翻转节点的前驱了

        ListNode node = prve.next;
        //需要翻转的次数是 right - left
        for (int i = 0; i < right - left; i++) {
            ListNode cur = node.next;//待翻转的节点
            node.next = cur.next;//跳过待翻转的节点连接下一个节点地址
            cur.next = prve.next;//头插
            prve.next = cur;//更新头插节点地址
        }
        return dummyHead.next;
    }

}

 */

/**
 * 思路三： 定义一个静态变量，让它执行翻转后末尾节点指向的地址，保留。
 * 末尾的节点分为两种情况，第一种是 后面不存在不需要翻转的节点，那么此刻的 next就应该是null
 * 第二种是 后面存在 不需要翻转的节点，如：1~5 我只翻转 2到4，那么 5 就是不需要翻转的节点，
 * 那么此刻的 next 保存的就是 5 的地址，这种情况发生在 left == right 时刻发生。
 */

public class Num_92_reverseBetween {

    //定义一个静态变量，让它执行翻转后末尾节点指向的地址，保留。
    public static ListNode next = null;
    public ListNode reverseBetween(ListNode head, int left, int right) {

        //终止条件
        if( head.next == null || left == right ){
            next = head.next;
            return head;
        }

        //如果此时头节点就需要翻转
        if(left == 1){
            ListNode prve = head;//需要我们手动尾插的头节点
            ListNode cur = prve.next;//等会翻转链表后的尾节点
            ListNode node = reverseBetween(head.next, left, right - -1);
            cur.next = prve;
            prve.next = next;

            return node;
        }

        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

}